package leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 题目：最大深度
 * 链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree/
 */
public class MaxDepth {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public static int maxDepth(TreeNode root) {
        int maxDepth = 0;
        maxDepth = depth(root, maxDepth);
        return maxDepth;
    }
    public static int depth(TreeNode treeNode, int maxDepth) {
        if(treeNode == null)
            return maxDepth;
        maxDepth++;
        if(treeNode.left == null || treeNode.right == null){
            TreeNode next = treeNode.left == null ? treeNode.right : treeNode.left;
            return depth(next, maxDepth);
        }else{
            return Math.max(depth(treeNode.left, maxDepth), depth(treeNode.right, maxDepth));
        }
    }

    public static void main(String[] args) {
//        Integer[] rootArray = {3, 9, 20, null, null, 15, 7};
        Integer[] rootArray = {1,null,2};
        TreeNode root = arrayToTree(rootArray);
        System.out.println(depth(root, 0));
    }

    public static TreeNode arrayToTree(Integer[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }

        TreeNode root = new TreeNode(nums[0]);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int i = 1;
        while (!queue.isEmpty() && i < nums.length) {
            TreeNode current = queue.poll();

            // 处理左子节点
            if (i < nums.length && nums[i] != null) {
                current.left = new TreeNode(nums[i]);
                queue.offer(current.left);
            }
            i++;

            // 处理右子节点
            if (i < nums.length && nums[i] != null) {
                current.right = new TreeNode(nums[i]);
                queue.offer(current.right);
            }
            i++;
        }

        return root;
    }
}
